package 栈;

import java.util.HashMap;
import java.util.Stack;

/**
 * @Author: LDeng
 * @Date: 2021-02-24 8:44
 * https://leetcode-cn.com/problems/valid-parentheses/
 */
public class _20_有效的括号 {

    private HashMap<Character,Character> map=new HashMap<>();

    public _20_有效的括号(){
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
    }

    public boolean isValid(String s){
        Stack<Character> stack=new Stack();
        int len=s.length();
        for(int i=0;i<len;i++){
            char c=s.charAt(i);
            if(map.containsKey(c)){
                stack.push(c);
            }else{//遇到了右括号
                if(stack.isEmpty()){//如果栈是空的 ， 返回false
                    return false;
                }
                char left=stack.pop();//弹出栈顶
                if(c!=map.get(left)) return false;//取出key lefe对应的value 和遍历的字符串比较， 不相等返回false
            }
        }
        return stack.isEmpty();
    }

    public boolean isValid1(String s){
        Stack<Character> stack=new Stack();
        int len=s.length();
        for(int i=0;i<len;i++){
            char c=s.charAt(i);
            if(c=='('||c=='['||c=='{'){
                stack.push(c);
            }else{//遇到了右括号
                if(stack.isEmpty()){//如果栈是空的 ， 返回false
                    return false;
                }
                char left=stack.pop();//弹出栈顶
                if(left=='(' && c!=')') return false;
                if(left=='[' && c!=']') return false;
                if(left=='{' && c!='}') return false;
            }
        }
        return stack.isEmpty();
    }

    public boolean isValid2(String s){
        while(s.contains("{}")
                ||s.contains("[]")
                ||s.contains("()")){
            s.replace("{}","");
            s.replace("[]","");
            s.replace("()","");
        }
        return s.isEmpty();
    }
}
